package com.daji.base_data_structure.Graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/* 
 * 这里的图只能存储int元素，就是原生的int类型的图。
 * 图中顶点的实际存储，从0开始，视pointCount决定，
 * 比如pointCount为5，那么这个图的顶点元素就是5个Integer：0，1，2，3，4
 */
public class Digraph {
    //顶点数目
    private final int pointCount;
    //边的数目
    private int edgeCount;
    //邻接表(二维数组)
    private List<Queue<Integer>> table;
    //标记数组:索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] markedArr;
    //是否有环（默认是无环的）
    private Boolean hasCycle = false;
    
    public Digraph(int V){
        //初始化顶点数量
        this.pointCount = V;
        //初始化边的数量
        this.edgeCount = 0;
        //初始化邻接表
        this.table = new ArrayList<>();
        //初始化标记数组（默认全都是false）
        this.markedArr = new boolean[pointCount];
        for (int i = 0; i < pointCount; i++) {
            //LinkedList实现了Queue，Queue是父，LinkedList是子，自动转换。
            //相当于 new Queue<Integer>
            //邻接表的每一个元素都存放了一个队列，该队列会存储和table[i]相链接的所有顶点
            table.add(new LinkedList<Integer>()); 
        }

    }


    //获取顶点数目
    public int getPointCount(){
        return pointCount;
    }

    //获取边的数目
    public int getEdgeCount(){
        return edgeCount;
    }

    //向有向图中添加一条边 v->w
    public void addEdge(int v, int w) {
        //只需要让顶点w出现在顶点v的邻接表中，因为边是有方向的，最终，顶点v的邻接表中存储的相邻顶点的含义是：  v->其他顶点
        table.get(v).offer(w);
        edgeCount++;
    }


    
    /**
     * 获取所有由point【指出】的顶点
     * @param point
     * @return
     */
    public Queue<Integer> getSpecificPointAllNeighbors(int point){
        return table.get(point);
    }

    //该图的反向图 （未实现）
    // private Digraph reverse(){
    //     //创建有向图对象
    //     Digraph r = new Digraph(pointCount);

    //     for (int v = 0;v<pointCount;v++){
    //         //获取由该顶点v指出的所有边
    //         for (Integer w : table[v]) {//原图中表示的是由顶点v->w的边

    //             r.addEdge(w,v);//w->v

    //         }

    //     }
    //     return r;
    // }

    /**
     * 判断有向图中是否有环
     * 如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。
     * 
     * 关键词：DFS
     * 使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，
     * 发现某个结点有一条边指向已访问过的结点，则表示存在环。
     * 
     * 思想：当一个结点正在DFS遍历的时候，对其进行标记。
     *      然后在DFS前，看看该结点继续指向谁，如果指向了已经标记过的结点，那么说明存在环
     *      如果指向的是没标记的结点，那么继续DFS
     *      当这个结点已经DFS过了（搜索完毕），将其取消标记
     * @return
     */
    public boolean hasCycle(){
        //初始化标记数组
        boolean[]circleMark = new boolean[pointCount];
        
        /* 
         * 遍历搜索图中的每一个顶点
         * 为什么有向图需要遍历搜索每个定点呢？无向图就不需要这么操作
         * 因为无向图相当于双向有向图，不管如何都可以指过去。
         * 但是有向图如果不挨个遍历，可能某个结点会出现【单相思】，只有它指别人，但是没人指它。
         */
        for (int i = 0; i < circleMark.length; i++) {
            if(!this.markedArr[i]){
                dfs(i,circleMark);
            }
            //如果已经检测到是有环了，接下来的遍历就不重要了，直接return true
            if (this.hasCycle == true) {
                return true;
            }
        }


        //擦屁股：将所有标记清空成false（因为markedArr是个全局变量）
        for (int i = 0; i < markedArr.length; i++) {
            this.markedArr[i] = false;
        }
        return this.hasCycle;
    }

    private void dfs(int i,boolean[] circleMark){
        circleMark[i] = true;       //【本次】搜索中，该结点是否被搜过。动态维护出入，是判断是否有环的依据
        this.markedArr[i] = true;   //【全局】标记该顶点是否被搜过的数组
        //访问该结点邻接表
        Queue<Integer> queue = this.table.get(i);
        for (Integer node : queue) {
            //如果邻接表的下一个指向元素已经出现在【本次】搜索过程中，那么说明有环。
            if(circleMark[node] == true){
                this.hasCycle = true;
                return;
            }
            //如果当前顶点没有被搜索过，则递归搜索与w顶点相通的其他顶点
            if(!this.markedArr[node]){
                dfs(node, circleMark);
            }
        }
        //当这个结点已经DFS过了（搜索完毕），将其取消标记
        circleMark[i] = false;
    }

    /**
     * 基于深度优先的拓扑排序
     * 拓扑排序概念：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，
     * 此时就可以明确的表示出每个顶点的优先级。
     *
     * 关键词：判断是否有环 + dfs
     * 
     * 拓扑排序必先保证该图无环，如果有环则不能拓扑排序。
     * 观察dfs算法，发现dfs会按照顺序不重复地访问所有结点。
     * 如果我们能在深度优先搜索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。
     * 
     * @return  完成拓扑排序的图构成的有序序列, 如果返回null，说明该图有环。
     */
    public List<Integer> topoLogical(){
        //拓扑排序必先保证该图无环，如果有环则不能拓扑排序。
        if (this.hasCycle()) {
            return null;    
        }
        //借助dfs进行拓扑排序
        ArrayList<Integer> topoList = new ArrayList<Integer>();
        /* 
         * 遍历搜索图中的每一个顶点
         * 为什么有向图需要遍历搜索每个定点呢？无向图就不需要这么操作
         * 因为无向图相当于双向有向图，不管如何都可以指过去。
         * 但是有向图如果不挨个遍历，可能某个结点会出现【单相思】，只有它指别人，但是没人指它。
         */
        for (int i = 0; i < this.pointCount; i++) {
            if(!this.markedArr[i]){
                dfsForTopo(i, topoList);
                topoList.add(i);
            }
        }
        //擦屁股：将所有标记清空成false（因为markedArr是个全局变量）
        for (int i = 0; i < markedArr.length; i++) {
            this.markedArr[i] = false;
        }        
        //返回翻转后的数组
        Collections.reverse(topoList);
        return topoList;
    }


    private void dfsForTopo(int i, ArrayList<Integer> topoList) {
        this.markedArr[i] = true;   //【全局】标记该顶点是否被搜过的数组
        //访问该结点邻接表
        Queue<Integer> queue = this.table.get(i);
        for (Integer node : queue) {
            //如果当前顶点没有被搜索过，则递归搜索与w顶点相通的其他结点
            if(!this.markedArr[node]){
                dfsForTopo(node, topoList);
                //递归dfs结束后向数组中添加该结点
                topoList.add(node);
            }
        }
    }


    

}
